package com.grape.dsaa.lineartable.queue.core;

import com.grape.dsaa.lineartable.queue.Queue;
/**
 * 描述:数组实现队列
 * @author: myx
 * @date: 2019-04-28
 * Copyright © 2019-grape. All rights reserved.
 */
public class MyArrayQueue<E> implements Queue<E> {

	private static final int DEFAULT_CAPACITY = 10;

	private E[] data; //存储队列元素的数组

	private int size; //队列元素数量

	private int head; //队头指针

	private int tail; //队尾指针

	public MyArrayQueue(int capacity) {
		this.data = (E[]) new Object[capacity];
		this.size = 0;
		this.head = -1;
		this.tail = -1;
	}

	public MyArrayQueue() {
		this(DEFAULT_CAPACITY);
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean empty() {
		return size == 0;
	}

	@Override
	public void enqueue(E e) {
		if(data.length == size)
		{
			grow(size*2);
		}

		tail = (tail + 1) % data.length;
		data[tail] = e;

		if(size == 0) {
			head = tail;
		}

		size++;
	}

	private void grow(int capacity) {
		if(capacity <= DEFAULT_CAPACITY){
			return;
		}

		E[] oldData = data;
		data = (E[]) new Object[capacity];

		for(int i=0; i<size; i++) {
			data[i] = oldData[(head + i)%oldData.length];
		}

		head = 0;
		tail = size - 1;

	}

	@Override
	public E dequeue() {
		if(size == 0) {
			throw new RuntimeException("队列为空...");
		}

		E result = data[head];

		head = (head + 1) % data.length;
		size--;

		if(size <= data.length/2) {
			grow(data.length/2);
		}

		return result;
	}

	@Override
	public E peek() {
		if(size == 0) {
			throw new RuntimeException("队列为空...");
		}

		return data[head];
	}
}
